package string;

/**
 * 给你一个字符串 s，找到 s 中最长的 回文 子串。
 * <p>
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * <p>
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 * @author Jisheng Huang
 * @version 20250518
 */
public class LongestPalindromeSubstr_5 {
    /**
     * Loop through both odd and even case of the string s. To find the longest palindrome string
     *
     * @param s the given string
     * @return the longest substring in s
     */
    public static String longestPalindrome(String s) {
        int len = s.length();

        // Edge case
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        // Take the minimum working example as the first character
        String res = s.substring(0, 1);

        // Loop through the whole string
        for (int i = 0; i < len - 1; ++i) {
            String oddStr = centerSpread(s, i, i);
            String evenStr = centerSpread(s, i, i + 1);
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;

            // Update the longest substr
            res = maxLenStr.length() > res.length() ? maxLenStr : res;
        }

        return res;
    }

    /**
     * Helper method the get the longest palindrome substring
     *
     * @param s     the given string
     * @param left  the left pointer
     * @param right the right pointer
     * @return the longest palindrome substring of the given string
     */
    public static String centerSpread(String s, int left, int right) {
        int n = s.length();
        int i = left;
        int j = right;

        while (i >= 0 && j < n) {
            if (s.charAt(i) == s.charAt(j)) {
                --i;
                ++j;
            } else {
                break;
            }
        }

        return s.substring(i + 1, j);
    }

    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome(s));

        s = "cbbd";
        System.out.println(longestPalindrome(s));
    }
}
